Edge List — Costs

• Space: The storage cost is directly proportional to the number of edges, making it very efficient for sparse graphs. The cost is $O(m)$, where $m = |E|$.
• Adjacency Test: To check if an edge $(u,v)$ exists, you must scan the entire list of $m$ edges in the worst case. This results in a slow $O(m)$ runtime.
• Neighbor Iteration: Similarly, finding all neighbors of a vertex $u$ requires a full scan of all edges to see which ones involve $u$. This is also an $O(m)$ operation.
• Add / Remove: Adding an edge is fast, typically $O(1)$ amortized time. Removing an edge requires first finding it, which takes $O(m)$ time unless the data structure is indexed.